package com.itheima;

import org.junit.Test;

import java.util.*;

public class MatrixProblem {

    public void setZeroes(int[][] matrix) {


        int m = matrix.length, n = matrix[0].length;
        Set<int[]> set = new HashSet<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 0) {
                    set.add(new int[]{i, j});
                }
            }
        }
        for(int[] arr : set) {
            int x = arr[0];
            int y = arr[1];
            for(int i = 0; i < m; i++) {
                matrix[i][y] = 0;
            }
            for(int i = 0; i < n; i++) {
                matrix[x][i] = 0;
            }
        }
        System.out.println(Arrays.deepToString(matrix));
    }

//    public List<Integer> spiralOrder(int[][] matrix) {
//        List<Integer> res = new ArrayList<>();
//        int m = matrix.length, n = matrix[0].length;
//
//        int i = 0, j = 0;
//        int w = 0; //表示圈数
//        while(w < m / 2 + 1) {
//            if(j == w && i - 1 == w) {
//                w++;
//                continue;
//            }
//            if(j < n - 1 - w && i == w) {
//                res.add(matrix[i][j]);
//                j++;
//            } else if(j == n - 1 - w && i < m - 1 - w) {
//                res.add(matrix[i][j]);
//                i++;
//            } else {
//                if(j > w) {
//                    res.add(matrix[i][j]);
//                    j--;
//                } else if(j == w && i > w) {
//
//                    res.add(matrix[i][j]);
//                    i--;
//
//                }
//            }
//        }
//
//        return res;
//    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        Set<List<Integer>> set = new HashSet<>(); //存储已经走过的路
        int i = 0, j = 0;
        int dir = 0; //表示方向
        set.add(Arrays.asList(new Integer[]{i, j}));
        res.add(matrix[i][j]);
        while(res.size() < m * n) {

//            if(!set.contains(Arrays.asList(i, j + 1)) && j + 1 < n) {
////                res.add(matrix[i][j]);
//                set.add(Arrays.asList(i, j + 1));
//                j++;
//            } else if(!set.contains(Arrays.asList(i + 1, j)) && i + 1 < m) {
//                set.add(Arrays.asList(i + 1, j));
//                i++;
//            } else if(!set.contains(Arrays.asList(i, j - 1)) && j - 1 >= 0) {
//                set.add(Arrays.asList(i, j - 1));
//                j--;
//            } else if(!set.contains(Arrays.asList(i - 1, j)) && i - 1 >= 0) {
//                set.add(Arrays.asList(i - 1, j));
//                i--;
//            }
            if(dir == 0) {
                if(j + 1 < n && !set.contains(Arrays.asList(i, j + 1))) {
                    set.add(Arrays.asList(i, j + 1));
                    j++;
                    res.add(matrix[i][j]);
                } else {
                    dir = 1;
                }
            }
            if(dir == 1) {
                if(i + 1 < m && !set.contains(Arrays.asList(i + 1, j))) {
                    set.add(Arrays.asList(i + 1, j));
                    i++;
                    res.add(matrix[i][j]);
                } else {
                    dir = 2;
                }
            }
            if(dir == 2) {
                if(j - 1 >= 0 && !set.contains(Arrays.asList(i, j - 1))) {
                    set.add(Arrays.asList(i, j - 1));
                    j--;
                    res.add(matrix[i][j]);
                }
                else {
                    dir = 3;
                }
            }
            if(dir == 3) {
                if(i - 1 >= 0 && !set.contains(Arrays.asList(i - 1, j))) {
                    set.add(Arrays.asList(i - 1, j));

                    i--;
                    res.add(matrix[i][j]);
                }
                else {
                    dir = 0;
                }
            }

        }
        return res;
    }

    public boolean searchMatrix(int[][] matrix, int target) {

        int m = matrix.length, n = matrix[0].length;
        int[][] dir = new int[][] {{1, 0}, {0, 1}};
        boolean res = false;

        int i = 0, j = 0;
        while(i < m && j < n) {
            if(matrix[i][j] == target) {
                res = true;
                break;
            }
            if(target > matrix[i][j]) {
                if(i + 1 < m && j + 1 < n) {
                    if(target >= matrix[i + 1][j] && target >= matrix[i][j + 1]) {
                        if(matrix[i + 1][j] > matrix[i][j + 1]) {
                            i++;
                        } else {
                            j++;
                        }
                    } else if(target < matrix[i][j + 1] && target >= matrix[i + 1][j]) {
                        i++;
                    } else if(target < matrix[i + 1][j] && target >= matrix[i][j + 1]) {
                        j++;
                    } else {
                        break;
                    }
                } else if(i + 1 < m) {
                    if(target >= matrix[i + 1][j]) {
                        i++;
                    } else {
                        break;
                    }
                } else if(j + 1 < n) {
                    if(target >= matrix[i][j + 1]) {
                        j++;
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            } else if(target < matrix[i][j]) {
                break;
            }

        }

        return res;
    }

    public void topic48(int[][] matrix) {
        int n = matrix[0].length;

        int i = 0, j = n - 1;
        while(i < j) {
            for(int k = 0; k < n; k++) {
                int tmp = matrix[i][k];
                matrix[i][k] = matrix[j][k];
                matrix[j][k] = tmp;
            }
            i++;
            j--;
        }
        for(int k = 0; k < n; k++) {
            for(int l = 0; l < k; l++) {
                int tmp = matrix[k][l];
                matrix[k][l] = matrix[l][k];
                matrix[l][k] = tmp;
            }
        }

    }
    public boolean topic240(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        boolean res = false;

        int i = 0, j = n - 1;
        while(i < m && j >= 0) {
            if(matrix[i][j] == target) {
                res = true;
                break;
            }
            if(i < m && j >= 0 && target > matrix[i][j]) {
                i++;
            }
            if(i < m && j >= 0 && target < matrix[i][j]) {
                j--;
            }
        }

        return res;
    }

    @Test
    public void test() {
//        setZeroes(new int[][]{{0,1,2,0},{3,4,5,2},{1,3,1,5}});

//        List<Integer> a = Arrays.asList(1, 2);
//        Set<List<Integer>> set = new HashSet<>();
//        set.add(a);
//        System.out.println(set.contains(Arrays.asList(1, 2)));
//        System.out.println(spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
//        searchMatrix(new int[][]{{1,4,7,11,15}, {2,5,8,12,19}, {3,6,9,16,22}, {10,13,14,17,24}, {18,21,23,26,30}}, 20);
        System.out.println(topic240(new int[][]{{1,4,7,11,15}, {2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24}, {18,21,23,26,30}}, 5));
    }


}
